Lista di adiacenza

Questa voce o sezione sull'argomento teoria dei grafi non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

In algebra computazionale, le liste di adiacenza sono una modalità di rappresentazione in memoria di grafi.

È probabilmente la rappresentazione più immediata a cui è possibile pensare e la più semplice da implementare, anche se in generale non la più efficiente in termini di spazio occupato.

L'idea della rappresentazione è semplicemente che ad ogni vertice ${\displaystyle V}$ viene associata una lista contenente tutti e soli i vertici ${\displaystyle W}$ tali che esista l'arco da ${\displaystyle V}$ a ${\displaystyle W}$.

Supponendo di memorizzare tutte le coppie del tipo (n, L), dove L è la lista di adiacenza del vertice n-esimo, si ottiene una descrizione univoca del grafo. In alternativa, se si stabilisce di ordinare le liste di adiacenza, non è necessario memorizzare esplicitamente anche gli indici n dei vertici.